package com.cqs.leetcode.dp;

import com.cqs.leetcode.IntsAndInt;

import java.util.ArrayList;
import java.util.List;

/**
 * lixw
 * 2021/11/5
 **/
public class TargetSum494 {

    static class BacktraceSolution {

        private int cnt = 0;

        public int findTargetSumWays(int[] nums, int target) {
            cnt = 0;
            backtrace(nums, 0, 0, target);
            return cnt;
        }

        private void backtrace(int[] nums, int idx, int tmp, int target) {
            if (idx == nums.length) {
                if (target == tmp) {
                    ++cnt;
                }
                return;
            }
            //使用+
            backtrace(nums, idx + 1, tmp + nums[idx], target);
            //使用-号
            backtrace(nums, idx + 1, tmp - nums[idx], target);
        }

        public static void main(String[] args) {
            BacktraceSolution s = new BacktraceSolution();
            List<IntsAndInt> list = new ArrayList<>();
            list.add(new IntsAndInt(new int[]{1, 1, 1, 1, 1}, 3));
            for (IntsAndInt c : list) {
                System.out.println(c + "\t" + s.findTargetSumWays(c.arr, c.target));
            }

        }
    }
}
